package org.xingole.leetcode.das.monostack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Problem Description: 
 * <a href="https://leetcode.com/problems/next-greater-element-ii/description/">
 * Next Greater Element II
 * </a>
 */
public class NextGreaterElementII {

     /*
      * Approach : Using Stack
      *
      * This stack stores the indices of the appropriate elements from nums array.
      * The top of the stack refers to the index of the Next Greater Element found
      * so far. We store the indices instead of the elements since there could be 
      * duplicates in the nums array. 
      *
      * We start traversing the nums array from right towards the left. For an element
      * nums[i] encountered, we pop all the elements stack[top] from the stack such 
      * that nums[stack[top]] <= nums[i]. We continue the popping till we encounter 
      * a stack[top] satisfying nums[stack[top]] > nums[i]. Now, it is obvious that the 
      * current stack[top] only can act as the Next Greater Element for nums[i] (right
      * now, considering only the elements lying to the right of nums[i]).
      *
      * If no element remains on the top of the stack, it means no larger element than 
      * nums[i] exists to its right. Along with this, we also push the index of the 
      * element just encountered (nums[i]), i.e i over the top of the stack, so that 
      * nums[i] (or stack[top]) now acts as the Next Greater Element for the elements
      * lying to its left.
      *
      * We go through two such passes over the complete nums array. This is done so as to
      * complete a circular traversal over the nums array. The first pass could make some 
      * wrong entries in the res array since it considers only the elements lying to 
      * the right of nums[i], without a circular traversal. But, these entries are corrected
      * in the second pass.
      *
      */
     public int[] nextGreaterElementsBackwards(int[] nums) {

          // Proof:
          // To show the correctness of the method, let's look at the following cases:
          // 
          // Assume that nums[j] is the correct Next Greater Element for nums[i], such 
          // that i < j <= stack[top]. Now, whenever we encounter nums[j], if
          // nums[j] > nums[stack[top]], it would have already popped the previous 
          // stack[top] and j would have become the topmost element. On the other hand,
          // if nums[j] < nums[stack[top]], it would have become the topmost element by 
          // being pushed above the previous stack[top]. In both cases, if nums[j] > nums[i],
          // it will be correctly determined to be the Next Greater Element.
          // 
          // After the first pass, there are a number of wrong entries (marked as -1) in 
          // the res array, because only the elements lying to the corresponding right
          // (no-circular) have been considered till now. 
          // After the second pass, the correct values are substitued.

          int n = nums.length;
          int[] res = new int[n];
          Deque<Integer> stack = new LinkedList<>();

          for ( int i = 2 * n - 1; i >= 0; --i ) {
               while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % n]) {
                    stack.pop();
               }
               res[i % n] = stack.isEmpty() ? -1 : nums[stack.peek()];
               stack.push(i % n);
          }

          return res;
     }

     public int[] nextGreaterElementsFrontwards(int[] nums) {

          // Loop invariant: the indices that haven't found the next greater number(
          // on its right) and the indices is sorted descendingly on the element number.
          int n = nums.length;
          int[] ret = new int[n];
          Arrays.fill(ret, -1);
          Deque<Integer> stack = new LinkedList<Integer>();

          // First loop to determine the right next greater number not circular way.
          // Second loop to determine the next greater number of the elements in the stack.
          for (int i = 0; i < n * 2 - 1; i++) {
               while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                    ret[stack.pop()] = nums[i % n];
               }
               stack.push(i % n);
          }
          return ret;
     }

}
